package Tree;

import org.junit.Test;

import java.security.Principal;
import java.util.*;

import static java.util.Collections.*;

/**
 * @author yyq
 * @create 2022-01-07 19:57
 *
 * 哈夫曼编码
 * 问题: I love you.
 *       以最简单的方式对 I,l,o,v,e,y,u,.,空格 进行编码传输
 *       例如 I:01, l:11 ....
 *
 * 解决办法:
 *  1. 统计各个字符出现的次数
 *  2. 构建哈夫曼树
 *  3. 按照左 0 ，右 1 输出各个字符的编码
 *
 *  哈夫曼树节点  data,frequency,left,right
 *
 */



public class HuffmanCode {
    @Test
    public void testByte(){
        String strByte = "10101000";
        System.out.println((byte)Integer.parseInt(strByte, 2));


    }
    public static String code="";
    public static HashMap<Byte,String> HaffumanCodeTable = new HashMap<>();
    public static void main(String[] args) {
        String input = "i like like like java do you like a java";
        byte[] bytes = haffumanZip(input);
        System.out.println(Arrays.toString(bytes));
        String s = haffumanUnZip(bytes);



    }
    /*
    *  功能:对压缩后的字节数组还原成字符串
    * */

    public static String haffumanUnZip(byte[] zip){
        String code="";
        for (int i = 0; i < zip.length; i++) {
            code=code+zip.toString();
        }


        return null;
    }

    /*
    *  功能: 输入字符串进行压缩，返回压缩后的字节数组
    * */
    public static byte[] haffumanZip(String input){
        byte[] bytes = input.getBytes();
        System.out.println("压缩前字节数:"+bytes.length);
        ArrayList<HuffmanNode> list = new ArrayList<>();
        list = getList(bytes);

        // 构建哈夫曼树 每次挑选两个最小的节点 组成一个新的节点 在放入list 重复 直达节点长度为1
        Integer length = list.size();
        HuffmanNode root = constructHuffmanTree(list,length);

        // 生成哈夫曼树编码表
        constructHuffmanCodeTable(root);

        System.out.println("遍历哈夫曼树:");
        preOrder(root);

        System.out.println("哈夫曼表:");
        for(Byte key:HaffumanCodeTable.keySet()){
            System.out.println("key:"+key+" "+"Value:"+HaffumanCodeTable.get(key));
        }

        // 将字符串对应的byte数组通过哈夫曼编码表进行压缩，输出哈夫曼编码表压缩后的byte数组
        byte[] zip=zip(bytes);
        System.out.println("压缩后的字节数:"+zip.length);

        return zip;
    }

    private static void Action(byte[] bytes) {
        ArrayList<HuffmanNode> list = new ArrayList<>();
        list = getList(bytes);

        // 构建哈夫曼树 每次挑选两个最小的节点 组成一个新的节点 在放入list 重复 直达节点长度为1
        Integer length = list.size();
        HuffmanNode root = constructHuffmanTree(list,length);

        // 生成哈夫曼树编码表
        constructHuffmanCodeTable(root);

        System.out.println("遍历哈夫曼树:");
        preOrder(root);

        System.out.println("哈夫曼表:");
        for(Byte key:HaffumanCodeTable.keySet()){
            System.out.println("key:"+key+" "+"Value:"+HaffumanCodeTable.get(key));
        }

        // 将字符串对应的byte数组通过哈夫曼编码表进行压缩，输出哈夫曼编码表压缩后的byte数组
        byte[] zip=zip(bytes);
        System.out.println("压缩后的字节数:"+zip.length);



    }

    /*
    *   功能：压缩
    *   输入: 源字符串转化为的bytes数组 byte[]  长度为40 需要40个字节来存储
    *   输出: 利用哈夫曼编码压缩后的byte[] 这里长度17
    *
    *   举例：
    *       字符串:i like like like java do you like a java
    *       对应的编码数据:10101000101111111100100010111111110010001011111111001001010011011100011100000110111010001111001010 00101111111100110001001010011011100
    *       此时该字符串长度133
    *       => byte[] haffumanCodeBytes => 每八位存进一个字节byte[i]
    *                   对于负数而言
    *                   haffumanCodeBytes[0] = 10101000 (补码)  =>  10101000- 1 = 10100111 (反码)  取反=> 11011000(原码)=-88
    * */
    private static byte[] zip(byte[] bytes) {
        // 1 利用哈夫曼编码表 将字节数组转化
        String code="";

        for (int i = 0; i < bytes.length; i++) {
            code=code+HaffumanCodeTable.get(bytes[i]);
        }


        int len;
        if(code.length()%8==0) len=code.length()/8;
        else len=code.length()/8+1;
        // 2 创建一个压缩后的byte数组
        byte[] zip=new byte[len];
        for (int i = 0; i < len; i++) {
            if(i*8+7>len){
                zip[i] = (byte) Integer.parseInt(code.substring(i*8,len),2);
                break;
            }
            zip[i] = (byte) Integer.parseInt(code.substring(i*8,i*8+7),2);
        }
        return zip;
    }

    public static void preOrder(HuffmanNode node){
        if(node.left==null&&node.right==null)
        System.out.println(node);
        if(node.left!=null) preOrder(node.left);
        if(node.right!=null) preOrder(node.right);
    }

    // 获得每个字符对应的哈夫曼表
    public static void constructHuffmanCodeTable(HuffmanNode root){

        if(root.left==null&&root.right==null){
            root.code= code;
            HaffumanCodeTable.put(root.b,root.code);
        }
        if(root.left!=null){
            code=code+"0";
            constructHuffmanCodeTable(root.left);
            code=code.substring(0,code.length()-1);
        }
        if(root.right!=null){
            code=code+"1";
            constructHuffmanCodeTable(root.right);
            code=code.substring(0,code.length()-1);
        }
    }


    // 构建哈夫曼树，返回根节点
    public static HuffmanNode constructHuffmanTree(ArrayList<HuffmanNode> list, Integer length) {
        while (length>1){
            HuffmanNode leftNode = list.get(0);
            HuffmanNode rightNode = list.get(1);
            list.add(new HuffmanNode('-', leftNode.frequency+rightNode.frequency,leftNode,rightNode ));
            // 踩坑 删除两次第一个 而不是 0 1
            list.remove(0);
            list.remove(0);
            Collections.sort(list);
            length--;
        }

        return list.get(0);
    }

    // 获得排序有序的节点list
    public static ArrayList<HuffmanNode> getList(byte[] bytes){
        ArrayList<HuffmanNode> list = new ArrayList<>();
        // 字符串进行扫描
        for (int i = 0; i < bytes.length; i++) {
            Boolean flag = true;
            // 查看列表里是否有该节点
            for (int j = 0; j < list.size(); j++) {
                if (bytes[i]==list.get(j).b){
                    list.get(j).frequency++;
                    flag = false;
                    break;
                }
            }
            // 没有添加该节点
            if(flag) list.add(new HuffmanNode(bytes[i],(char) bytes[i], 1));
        }
        // 对节点频数进行排序 从小到大
        Collections.sort(list);
        System.out.println();

        return list;
    }
}


class HuffmanNode implements Comparable<HuffmanNode>{
    public HuffmanNode(char data, Integer frequency, HuffmanNode left, HuffmanNode right) {
        this.data = data;
        this.frequency = frequency;
        this.left = left;
        this.right = right;
    }

    public HuffmanNode(byte b,char data, Integer frequency) {
        this.b=b;
        this.data = data;
        this.frequency = frequency;
    }
    byte b;
    char data;
    Integer frequency;
    String code;
    HuffmanNode left;
    HuffmanNode right;

    @Override
    public int compareTo(HuffmanNode o) {
        if(this.frequency>o.frequency) return 1;
        else if (this.frequency<o.frequency) return -1;
        else return 0;
    }

    @Override
    public String toString() {
        return "HuffmanNode{" +
                "b=" + b +
                ", data=" + data +
                ", frequency=" + frequency +
                ", code=" + code +"}";
    }
}
